密码学中的模乘算法——蒙哥马利模乘（Montgomery Modular Multiplication）
在密码学中，最常见的一类运算大概就是模算术(Modular Arithmetic)了。特别地，模乘(Modular Multiplication)是其中最复杂的基本运算。这里记录自己对一种重要的模乘算法---蒙哥马利模乘[1]的理解。
概述
蒙哥马利模乘最主要的贡献就是提供了一种给定输入 ，快速计算 的模约减方法。为了描述方便将该模约减方法记为 。现在定义一个整数 的蒙哥马利形式(Montgomery form, Montgomery domain)为 。显然，一个整数 的蒙哥马利形式可以先算一次乘法 最后算一次 得到，即 。
现在考虑如何计算两个整数 和 的模乘，即 。这里利用蒙哥马利模乘达成这个计算目标。蒙哥马利模乘可以分三步进行计算。
1. 将输入 转成蒙哥马利形式，即 ,。
2. 做一次标准乘法得。
3. 最后做一次REDC得 。
4. 注意上面三个步骤返回的是蒙哥马利形式的 ，即 。若需要转换成正常形式的 ，需要再做一次得 。
蒙哥马利模约简
现在讨论蒙哥马利模乘最重要的部分REDC。下面给出 的算法描述:
一般地，想做模约减运算，需要做一次试除，即 。 REDC的核心思想是避免做除法 , 但是仍能求得模约减的结果。作为代价, REDC算的模约减结果包含了一个'尾巴' 。这也是为什么蒙哥马利模乘算法当中反复强调要在蒙哥马利形式下进行的根本原因。
接着，我们讨论构造REDC算法当中的直觉。注意REDC算法的输入是 。 我们希望 加上 的某个整数倍恰好能被 整除，即 是一个整数。通过巧妙地选择参数使得 是一个比较小（小于 ）的整数, 且 。
最后我们正式地证明REDC算法的正确性。容易分析出证明REDC是正确的，只需证明下面三个性质成立:
1. 被 整除。
证明:
2. 。
证明:
3. 。
证明:
易知
代码实现
最后给出一个蒙哥马利模乘的Python实现以供参考。注意程序里面取 , 所以相当于取低64bit； 相当于右移64bit。
import math
class MontMul:
"""docstring for ClassName"""
def __init__(self, R, N):
self.N = N
self.R = R
self.logR = int(math.log(R, 2))
N_inv = MontMul.modinv(N, R)
self.N_inv_neg = R - N_inv
self.R2 = (R*R)%N
@staticmethod
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = MontMul.egcd(b % a, a)
return (g, x - (b // a) * y, y)
@staticmethod
def modinv(a, m):
g, x, y = MontMul.egcd(a, m)
if g != 1:
raise Exception('modular inverse does not exist')
else:
return x % m
def REDC(self, T):
N, R, logR, N_inv_neg = self.N, self.R, self.logR, self.N_inv_neg
m = ((T&int('1'*logR, 2)) * N_inv_neg)&int('1'*logR, 2) # m = (T%R * N_inv_neg)%R
t = (T+m*N) >> logR # t = int((T+m*N)/R)
if t >= N:
return t-N
else:
return t
def ModMul(self, a, b):
if a >= self.N or b >= self.N:
raise Exception('input integer must be smaller than the modulus N')
R2 = self.R2
aR = self.REDC(a*R2) # convert a to Montgomery form
bR = self.REDC(b*R2) # convert b to Montgomery form
T = aR*bR # standard multiplication
abR = self.REDC(T) # Montgomery reduction
return self.REDC(abR) # covnert abR to normal ab
if __name__ == '__main__':
N = 123456789
R = 2**64 # assume here we are working on 64-bit integer multiplication
g, x, y = MontMul.egcd(N,R)
if R<=N or g !=1:
raise Exception('N must be larger than R and gcd(N,R) == 1')
inst = MontMul(R, N)
input1, input2 = 23456789, 12345678
mul = inst.ModMul(input1, input2)
if mul == (input1*input2)%N:
print ('({input1}*{input2})%{N} is {mul}'.format(input1 = input1, input2 = input2, N = N, mul = mul))本文参考
[1]https://en.wikipedia.org/wiki/Montgomery_modular_multiplication
本文作者：hujwei
知乎链接：https://zhuanlan.zhihu.com/p/581656171
往期推荐
1.笔记分享 | 组队学习密码学（2）——密码学在联邦学习中的应用
2.笔记分享 | 冯登国院士MPC讲座（3）——基于混淆电路方法的安全多方计算协议会议信息 | 2023年6月截稿的密码学与信息安全会议整理4.论文分享 | Endemic Oblivious Transfer via Random Oracles, Revisited